/**
 * 42. 接雨水
 * https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked
 */
class Solution2 {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int left_max = 0, right_max = 0, ret = 0;
        while(left < right) {
            if(height[left] < height[right]) {
                if(height[left] > left_max) {
                    left_max = height[left];
                } else {
                    ret += left_max - height[left];
                }
                left++;
            } else {
                // height[left] > height[right]
                if(height[right] > right_max) {
                    right_max = height[right];
                } else{
                    ret += right_max - height[right];
                }
                right--;
            }
        }
        return ret;
    }
}